package datastructure.book.dp._1_pathway.all;

import org.junit.jupiter.api.Test;

public class _2_Solution {
    int[][] cntArr;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
            return 0;
        }
        cntArr = new int[obstacleGrid.length][obstacleGrid[0].length];
        cntArr[obstacleGrid.length-1][obstacleGrid[0].length-1] = 1;
        uniquePathsWithObstacles(obstacleGrid,0,0);
        return cntArr[0][0];
    }
    private boolean uniquePathsWithObstacles(int[][] arr,int i,int j) {
        if (i > arr.length - 1 || j > arr[0].length - 1) {
            return false;
        }
        if (arr[i][j] == 1) {
            return false;
        }
        if (i + 1 < arr.length) {
            if (cntArr[i + 1][j] != 0) {
                cntArr[i][j]+=cntArr[i + 1][j];
            } else if (uniquePathsWithObstacles(arr, i + 1, j)) {
                cntArr[i][j]+=cntArr[i + 1][j];
            }
        }
        if (j + 1 < arr[0].length) {
            if (cntArr[i][j + 1] != 0) {
                cntArr[i][j]+=cntArr[i][j + 1];
            } else if (uniquePathsWithObstacles(arr, i, j + 1)) {
                cntArr[i][j]+=cntArr[i][j + 1];
            }
        }
        return true;
    }

    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int[][] arr = new int[obstacleGrid.length][obstacleGrid[0].length];
        if (obstacleGrid[arr.length - 1][arr[0].length - 1] == 1) {
            return 0;
        }
        arr[0][0] = 1;
        for (int i = 0; i <obstacleGrid.length ; i++) {
            for (int j = 0; j < obstacleGrid[0].length; j++) {
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }
                if (i > 0 && j > 0) {
                    arr[i][j] = arr[i-1][j]+arr[i][j-1];
                } else if (i > 0) {
                    arr[i][j] = arr[i-1][j];
                } else if (j > 0) {
                    arr[i][j] = arr[i][j-1];
                }
            }
        }
        return arr[arr.length - 1][arr[0].length - 1];
    }

    @Test
    public void testUniquePathsWithObstacles2(){
        System.out.println(uniquePathsWithObstacles2(new int[][]{
                {0,0,1}, {0,1,0}, {0,0,0}}));
    }
}
